4. HTMLを解析する──HTMLからDOMツリーへの変換

HTML をブラウザに実装するとは、HTML で書かれた文字列を解釈し、解釈した文字列を画面に描画するということ

文字列を解釈するとは、文字列を小さな意味のある単位に分割（字句解析）し、その分解された要素の構造や階層関係を解析（構文解析）すること

HTML 言語に限らず、プログラミング言語や他のマークアップ言語を実装する際にも、このプロセスは行われる

HTML の字句解析

HTML の文字列を分割するためのアルゴリズムは、HTML Living Standard 13.2.5 Tokenization で決められている

アルゴリズムは以下のようなステートマシンとして表現される

code:mermaid

https://scrapbox.io/files/6739e231da86f4525b6c3640.png

HTML の文字列を 1 文字ずつ処理していく、現在の状態と次に処理する 1 文字によって状態の更新とトークン（HTML トークン）の生成が行われる

トークンは 6 種類存在するが、本書では 4 種類のみ扱う

残り: 1. ブラウザを知る──Webサイトを表示するアプリケーション#6732fd4675d04f000014d315

DOCTYPE

状態は 80 種類存在するが、本書では 17 種類のみ扱う

Data

初期状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が < であれば、状態を Tag open に変更する

EOF に到達した場合、 EOF トークンを返し、それ以外は文字トークンを返す

Tag open: タグが開始している状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が / の場合、状態を End tag open に変更する

文字がアルファベットの場合、以下を行う

文字を再度取り扱うためのフラグ（reconsume）を true に

4. HTMLを解析する──HTMLからDOMツリーへの変換#673ad6f875d04f00006889bd

状態を TagName に変更する

開始タグトークンを生成する

EOF に到達した場合、 EOF トークンを返す

それ以外は reconsume を true にし、状態を Data に戻す

End tag open: 終了タグを扱うための状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がアルファベットの場合、以下を行う

reconsume を true にする

状態を Tag name に変更する

終了タグトークンを生成する

EOF に到達した場合、 EOF トークンを返す

Tag name: タグの名前を扱う状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がホワイトスペースの場合、状態を Before attribute name に変更する

文字が / の場合、状態を Self-closing start tag に変更する

文字が > の場合、以下を行う

状態を Data に戻す

現在（一番最後に生成した）の開始タグ or 終了タグのトークンを返す

文字がアルファベットの場合、文字を現在のタグ（トークン）の名前として追加する

EOF に到達した場合、 EOF トークンを返す

Before attribute name: タグの属性名を処理する前の状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が / か >、または EOF に到達した場合、以下を行う

reconsume を true にする

状態を After attribute name に変更する

上記以外の場合、以下を行う

reconsume を true にする

状態を Attribute name に変更する

現在の開始タグトークンに属性を追加する

Attribute name: タグの属性名を処理している状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がホワイトスペースか、/、 >、または EOF に到達した場合、以下を行う

reconsume を true にする

状態を After attribute name に変更する

文字が = の場合、以下を行う

状態を Before attribute value 状態に変更する

文字を現在の属性の名前として追加する

After attribute name: タグの属性名を処理した後の状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がホワイトスペースの場合、無視する

文字が / の場合、状態を Self-closing start tag に変更する

文字が = の場合、状態を Before attribute value に変更する

文字が > の場合、以下を行う

状態を Data に変更する

現在の開始タグトークンを返す

EOF に到達した場合、 EOF トークンを返す

上記以外の場合、以下を行う（Before attribute name と同様）

reconsume を true にする

状態を Attribute name に変更する

現在の開始タグトークンに属性を追加する

Before attribute value: タグの属性値を処理する前の状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がホワイトスペースの場合、無視する

文字が " の場合、状態を Attribute value double-quoted に変更する

文字が ' の場合、状態を Attribute value single-quoted に変更する

上記以外の場合、以下を行う

reconsume を true にする

状態を Attribute value unquoted にする

Attribute value double-quoted: " で囲まれたタグの属性値を処理する状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が " の場合、状態を After attribute value quoted に変更する

EOF に到達した場合、 EOF トークンを返す

上記以外の場合、文字を現在の属性の値として追加する

Attribute value single-quoted: ' で囲まれたタグの属性値を処理する状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が ' の場合、状態を After attribute value quoted に変更する

EOF に到達した場合、 EOF トークンを返す

上記以外の場合、文字を現在の属性の値として追加する

Attribute value unquoted: " や ' で囲まれていない属性値を処理する状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がホワイトスペースの場合、状態を Before attribute name に変更する

文字が > の場合、以下を行う

状態を Data に変更する

現在の開始タグトークンを返す

EOF に到達した場合、 EOF トークンを返す

上記以外の場合、文字を現在の属性の値として追加する

After attribute value quoted: 属性値を処理した後の状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がホワイトスペースの場合、状態を Before attribute name に変更する

文字が / の場合、状態を Self-closing start tag に変更する

文字が > の場合、以下を行う

状態を Data に変更する

現在の開始タグトークンを返す

EOF に到達した場合、 EOF トークンを返す

上記以外の場合、以下を行う

reconsume を true にする

状態を Before attribute value に変更する

Self-closing start tag: 自己終了タグを処理する状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が > の場合、以下を行う

状態を Data に変更する

現在の開始タグトークンを、自己終了タグであることを表すフラグをオンにして返す

EOF に到達した場合、 EOF トークンを返す

以下は定義しているが、上記の状態から遷移することが無いので遷移することはないのでは…?? radish-miyazaki.icon

Script data: <script> タグ内に書かれている JavaScript を処理する状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が < の場合、状態を Script data less-than sign に変更する

EOF に到達した場合、 EOF トークンを返す

上記以外の場合、文字トークンを返す

Script data less-than sign: 開始タグ <script> の中で < が出てきたときの状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が / の場合、以下を行う

Temporary buffer をリセットする

4. HTMLを解析する──HTMLからDOMツリーへの変換#673b0a5e75d04f000017b8d3

状態を Script data end tag open に変更する

上記以外の場合、以下を行う

reconsume を true にする

状態を Script data に変更する

文字トークン（>）を返す

Script data end tag open: 終了タグ </script> を処理する前の状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字がアルファベットの場合、以下を行う

reconsume を true にする

状態を Script data end tag name に変更する

終了タグトークンを作成する

上記以外の場合、以下を行う

reconsume を true にする

状態を Script data に変更する

文字トークン（< と /）を返す

Script data end tag name: 終了タグ </script> のタグ名を解析している状態

1 つの文字を消費し、その種類によって次の行動を決定する

文字が > の場合、以下を行う

状態を Data に変更する

終了タグ（</script>）トークンを返す

文字がアルファベットの場合、以下を行う

reconsume を true にする

文字を Temporary buffer と現在のタグ（トークン）の名前として追加する

上記以外の場合、Temporary buffer に </ と文字を追加した後、バッファ内の文字をバッファに入った順に文字トークンとして返す

その後、reconsume を true にし、状態を Script data に変更する

Reconsume

When a state says to reconsume a matched character in a specified state, that means to switch to that state, but when it attempts to consume the next input character, provide it with the current input character instead.

Tokenization の仕様書で繰り返し出てくるワード①

状態だけを更新し、使用した文字をもう一度解析することを指す

そのため、実装時にはフラグなどで値を保持しておく必要がある

Temporary buffer

Certain states also use a temporary buffer to track progress, and the character reference state uses a return state to return to the state it was invoked from.

Tokenization の仕様書で繰り返し出てくるワード②

実装を簡単にするために、一時的なバッファを保持する状態

仕様書に状態としては分類されていない

HTML の構文解析

字句解析されたトークンを利用して、構文解析により DOM ツリーを構築する

DOM ツリーを構築するノードは、それぞれの HTML タグを表す

ノードは Node インタフェースを実装するオブジェクトである

Node インタフェースでは、要素を追加する appendChild や insertBefore などのメソッドが定義されている

ノードの種類（Node インタフェースを継承したインタフェース）

Document インタフェース: HTML 文書の DOM ツリーのルートを表す

既存の要素を取得する getElementById や getElementsByClassName などを持つ

warning.icon 厳密には、getElementByIdは Document インタフェースで定義されているのではなく、Document インタフェースがミックスインしている別のインタフェース（NonElementParentNode インタフェース）で定義されている

Element インタフェース: DOM ツリー内の要素ノードを表す

e.g. <p> など

インタフェース内で定義されている tagName や id、className を使用して、要素のタグ名や ID、クラス名を取得したり、getAttribute メソッドで要素の属性を取得することが可能

Text インタフェース: 要素内のテキストコンテンツを表す

Window オブジェクト: スクリプトを実行しているブラウザのウィンドウを表すオブジェクト

DOM ツリーのルートを持つ

1 つの Web ページに対して 1 つのインスタンスが存在する

ただし、iframe は独自の Window オブジェクトを持つ

JavaScript では、window というグローバル変数で定義されており、Devtools から確認できる

https://scrapbox.io/files/673ddc1f6c8b2a35b0f13ab4.png

DOM ツリーを構築するアルゴリズムは HTML Living Standard 13.2.6 Tree construction で決められている

このアルゴリズムでは、トークン列を入力とし、状態を切り替えながらトークンを 1 つずつ処理し、DOM ツリーを拡張させることで DOM ツリーを構築する

これは、字句解析と同様にステートマシンによるアルゴリズムである

HTML Living Standard 13.2.4.1 The insertion mode では 23 種類の状態が定義されているが、本書では 9 種類だけ実装する

Initial: DOCTYPE トークンを取り扱う

Before html: <html> の開始タグを取り扱う

1 つのトークンを消費し、その種類によって次の行動を決定する

空白文字や改行文字の場合、そのトークンは無視する

<html> の開始タグの場合、以下を行う

The stack of open elements に新しいノード（html Element）を追加

The stack of open elements

現在開かているすべての Element を追跡し、正しいツリー構造を構築するためにブラウザが用いるスタック（FIFO）

Initial 時点では空

その後、パース中に開始タグが現れるとそのノードをスタックに追加し、終了タグが現れるとスタックから除去する

これにより、要素の親子関係の管理が可能

次の状態（Before head）に遷移

EOF の場合、構築したツリーを返す

上記以外の場合、トークンが <html> の開始タグの場合と同様の処理を行う

これにより、 <html> を省略した場合でもパース可能に

Before head: <head> の開始タグを取り扱う

1 つのトークンを消費し、その種類によって次の行動を決定する

空白文字や改行文字の場合、そのトークンは無視する

<head> の開始タグの場合、以下を行う

The stack of open elements に新しいノード（head Element）を追加

次の状態（In head）に遷移

EOF の場合、構築したツリーを返す

上記以外の場合、トークンが <head> の開始タグの場合と同様の処理を行う

これにより、 <head> を省略した場合でもパース可能に

In head: <head> の終了タグや <style>、<script> の開始タグを取り扱う

1 つのトークンを消費し、その種類によって次の行動を決定する

空白文字や改行文字の場合、そのトークンは無視する

warning.icon 仕様書ではこれらの取り扱いは異なるが、ここでは同じにする

The stack of open elements に新しいノード（style / head Element）を追加

Text 状態に遷移

original insertion mode に現在の状態（In head）をセットする

original insertion mode

とある状態に遷移したときに、以前の挿入モードを保存するために用いられる

<head> の終了タグの場合、以下を行う

The stack of open elements からノード（head Element）を削除

次の状態（After head）に遷移

上記以外の場合、無視する

これにより、<head> タグ中にサポートしていないタグが出てきた場合も正しくパーサを動作させるためである

warning.icon 仕様書とは異なるが、本書ではすべてのタグを実装するのが難しいので、このような実装をしている

After head: WIP...

アルゴリズム開始時点では、DOM ツリーは Document オブジェクトのみ、状態は Initial 状態からスタートする

Initial 状態のときに HTML トークンを受け取ると、Before html 状態に遷移し、再び HTML トークンを処理する

Before html 状態で HTML トークンを受け取ると、HTML 要素を作成しツリーに追加する

e.g. たとえば以下の HTML は、次の図のように遷移する

code:html

<body>

<h1>Hello world</h1>

</body>

code:mermaid

stateDiagram-v2

* --> Initial

Initial --> BeforeHtml

note left of BeforeHtml: Html Element を追加する

BeforeHtml --> BeforeHead

note right of BeforeHead: Head Element を追加する

BeforeHead --> InHead

InHead --> AfterHead

note left of AfterHead: Body Element を追加する

AfterHead --> InBody

note right of InBody: H1 Element とテキストを追加する

InBody --> InBody

InBody --> AfterBody

AfterBody --> AfterAfterBody

AfterAfterBody --> *

Rust における循環参照問題

循環参照とは？

オブジェクト同士が互いに参照し合う状態

発生するとどうなる？

循環参照が発生すると、メモリ管理やオブジェクトの解放が困難になる場合がある

通常、オブジェクトは参照されなくなった時点で GC などにより自動的に解放される

しかし、循環参照の場合は、どのオブジェクトも常に参照され続けるため、解放されずにメモリを専有し続ける

回避策

弱い参照（ウィークポインタ）や強い参照（ストロングポインタ）などを使用して、参照関係を管理する

これにより、循環参照が発生しても参照の解除が正しく行われ、メモリリークを防げる

具体的には、ウィークポインタはストロングポインタの参照カウンタが 0 になったときに削除される

Rust ではどう回避するか

https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html#循環参照を回避する-rctをweaktに変換する

強い参照は Rc、弱い参照は Weak を使用して使い分けることが可能

Weak は Rc::downgrade を用いて生成するのが一般的

code:rs

pub struct Node {

pub kind: NodeKind,

window: Weak<RefCell<Window>>,

parent: Weak<RefCell<Node>>,

first_child: Option<Rc<RefCell<Node>>>,

last_child: Weak<RefCell<Node>>,

previous_sibling: Weak<RefCell<Node>>,

next_sibling: Option<Rc<RefCell<Node>>>,

}

子ノードや兄弟ノードへの参照は、データ構造の所有権に近い役割を持つため Rc を用いている

それ以外のノードでは循環参照を避けるため、Weak を用いる

https://scrapbox.io/files/673dd586b6b8c70e152c6cd7.png